<!DOCTYPE html>
<html class="client-nojs vector-feature-night-mode-disabled vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-sticky-header-enabled" lang="en" dir="ltr"><head>
<meta charset="UTF-8">
<title>Subadditive set function</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="canonical" href="https://en.wikipedia.org/wiki/Subadditive_set_function"> <link href="./mw/ext.cite.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/user.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link rel="stylesheet" type="text/css" href="./mw/site.styles.css">
<link rel="stylesheet" type="text/css" href="./mw/noscript.css">
<link rel="stylesheet" type="text/css" href="./footer.css">
<link rel="stylesheet" type="text/css" href="./vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Subadditive_set_function rootpage-Subadditive_set_function skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading">
<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Subadditive set function</span></span>
</h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p>In mathematics, a <b>subadditive set function</b> is a <a href="Set_function" title="Set function">set function</a> whose value, informally, has the property that the value of function on the union of two sets is at most the sum of values of the function on each of the sets. This is thematically related to the <a href="Subadditivity" title="Subadditivity">subadditivity</a> property of real-valued functions.
</p>
<meta property="mw:PageProp/toc">
<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>
<p>Let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi mathvariant="normal">Ω<!-- Ω --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \Omega }</annotation>
</semantics>
</math></span><img src="./24b0d5ca6f381068d756f6337c08e0af9d1eeb6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Omega }" loading="lazy"></span> be a <a href="Set_(mathematics)" title="Set (mathematics)">set</a> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\colon 2^{\Omega }\rightarrow \mathbb {R} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>f</mi>
<mo>:<!-- : --></mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="normal">Ω<!-- Ω --></mi>
</mrow>
</msup>
<mo stretchy="false">→<!-- → --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">R</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f\colon 2^{\Omega }\rightarrow \mathbb {R} }</annotation>
</semantics>
</math></span><img src="./1a4641e826c6eaec6bd2eb36e6ffc3bd307fcaec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.186ex; height:3.009ex;" alt="{\displaystyle f\colon 2^{\Omega }\rightarrow \mathbb {R} }" loading="lazy"></span> be a <a href="Set_function" title="Set function">set function</a>, where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{\Omega }}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="normal">Ω<!-- Ω --></mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{\Omega }}</annotation>
</semantics>
</math></span><img src="./56c53a10995552345e60c76e601ae3afdbd49158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.581ex; height:2.676ex;" alt="{\displaystyle 2^{\Omega }}" loading="lazy"></span> denotes the <a href="Power_set#Representing_subsets_as_functions" title="Power set">power set</a> of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi mathvariant="normal">Ω<!-- Ω --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \Omega }</annotation>
</semantics>
</math></span><img src="./24b0d5ca6f381068d756f6337c08e0af9d1eeb6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Omega }" loading="lazy"></span>. The function <i>f</i> is <i>subadditive</i> if for each subset <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>S</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle S}</annotation>
</semantics>
</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>T</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle T}</annotation>
</semantics>
</math></span><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"></span> of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi mathvariant="normal">Ω<!-- Ω --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \Omega }</annotation>
</semantics>
</math></span><img src="./24b0d5ca6f381068d756f6337c08e0af9d1eeb6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Omega }" loading="lazy"></span>, we have <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(S)+f(T)\geq f(S\cup T)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>f</mi>
<mo stretchy="false">(</mo>
<mi>S</mi>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>f</mi>
<mo stretchy="false">(</mo>
<mi>T</mi>
<mo stretchy="false">)</mo>
<mo>≥<!-- ≥ --></mo>
<mi>f</mi>
<mo stretchy="false">(</mo>
<mi>S</mi>
<mo>∪<!-- ∪ --></mo>
<mi>T</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f(S)+f(T)\geq f(S\cup T)}</annotation>
</semantics>
</math></span><img src="./94a2880996ace6432918edbceb6483e877146ffb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.056ex; height:2.843ex;" alt="{\displaystyle f(S)+f(T)\geq f(S\cup T)}" loading="lazy"></span>.<sup id="cite_ref-UF_1-0" class="reference"><a href="#cite_note-UF-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-DNS_2-0" class="reference"><a href="#cite_note-DNS-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Note that by substitution of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T=S}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>T</mi>
<mo>=</mo>
<mi>S</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle T=S}</annotation>
</semantics>
</math></span><img src="./1fb05877dbd011ec1a77e1ed0f3d905d42372c1d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.234ex; height:2.176ex;" alt="{\displaystyle T=S}" loading="lazy"></span> into the defining equation, it follows that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(S)\geq 0}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>f</mi>
<mo stretchy="false">(</mo>
<mi>S</mi>
<mo stretchy="false">)</mo>
<mo>≥<!-- ≥ --></mo>
<mn>0</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f(S)\geq 0}</annotation>
</semantics>
</math></span><img src="./cb5ff5e4365f6efd6303714dc6a4b0e568830eb7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.848ex; height:2.843ex;" alt="{\displaystyle f(S)\geq 0}" loading="lazy"></span> for all <span class="nowrap"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>S</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle S}</annotation>
</semantics>
</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span></span>.
</p>
<div class="mw-heading mw-heading2"><h2 id="Examples_of_subadditive_functions">Examples of subadditive functions</h2></div>
<p><br>
Every non-negative <a href="Submodular_set_function" title="Submodular set function">submodular set function</a> is subadditive (the family of non-negative submodular functions is strictly contained in the family of subadditive functions).
</p><p>The function that counts the number of sets required to <a href="Set_cover" class="mw-redirect" title="Set cover">cover</a> a given set is subadditive. Let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1},\dotsc ,T_{m}\subseteq \Omega }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>T</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<msub>
<mi>T</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>m</mi>
</mrow>
</msub>
<mo>⊆<!-- ⊆ --></mo>
<mi mathvariant="normal">Ω<!-- Ω --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle T_{1},\dotsc ,T_{m}\subseteq \Omega }</annotation>
</semantics>
</math></span><img src="./c059e7547308a747e79c40aaf600b46392ee15eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.399ex; height:2.509ex;" alt="{\displaystyle T_{1},\dotsc ,T_{m}\subseteq \Omega }" loading="lazy"></span> such that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \cup _{i=1}^{m}T_{i}=\Omega }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msubsup>
<mo>∪<!-- ∪ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>m</mi>
</mrow>
</msubsup>
<msub>
<mi>T</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>=</mo>
<mi mathvariant="normal">Ω<!-- Ω --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \cup _{i=1}^{m}T_{i}=\Omega }</annotation>
</semantics>
</math></span><img src="./c9e5b4920b51cad2c51a74043137adf191a1ba85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.384ex; height:2.843ex;" alt="{\displaystyle \cup _{i=1}^{m}T_{i}=\Omega }" loading="lazy"></span>. Define <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>f</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f}</annotation>
</semantics>
</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> as the minimum number of subsets required to cover a given set. Formally, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(S)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>f</mi>
<mo stretchy="false">(</mo>
<mi>S</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f(S)}</annotation>
</semantics>
</math></span><img src="./99a865d36b32ea1d60f15dc3093f5b28093f192b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.587ex; height:2.843ex;" alt="{\displaystyle f(S)}" loading="lazy"></span> is the minimum number <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>t</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle t}</annotation>
</semantics>
</math></span><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"></span> such that there are sets <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{i_{1}},\dotsc ,T_{i_{t}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>T</mi>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>i</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
</mrow>
</msub>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<msub>
<mi>T</mi>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>i</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>t</mi>
</mrow>
</msub>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle T_{i_{1}},\dotsc ,T_{i_{t}}}</annotation>
</semantics>
</math></span><img src="./032ec7ac56c3d2b16548262fb41f5c8d671510e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.97ex; height:2.843ex;" alt="{\displaystyle T_{i_{1}},\dotsc ,T_{i_{t}}}" loading="lazy"></span> satisfying <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\subseteq \cup _{j=1}^{t}T_{i_{j}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>S</mi>
<mo>⊆<!-- ⊆ --></mo>
<msubsup>
<mo>∪<!-- ∪ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>j</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>t</mi>
</mrow>
</msubsup>
<msub>
<mi>T</mi>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>i</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>j</mi>
</mrow>
</msub>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle S\subseteq \cup _{j=1}^{t}T_{i_{j}}}</annotation>
</semantics>
</math></span><img src="./e647d23bf0d6b1190f38c448378f5fb22397df39.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:12.03ex; height:3.509ex;" alt="{\displaystyle S\subseteq \cup _{j=1}^{t}T_{i_{j}}}" loading="lazy"></span>. Then <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>f</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f}</annotation>
</semantics>
</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> is subadditive.
</p><p>The <a href="Maximum" class="mw-redirect" title="Maximum">maximum</a> of <a href="Additive_map" title="Additive map">additive set functions</a> is subadditive (dually, the <a href="Minimum" class="mw-redirect" title="Minimum">minimum</a> of additive functions is <a href="Superadditive" class="mw-redirect" title="Superadditive">superadditive</a>). Formally, for each <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in \{1,\dotsc ,m\}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>i</mi>
<mo>∈<!-- ∈ --></mo>
<mo fence="false" stretchy="false">{</mo>
<mn>1</mn>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<mi>m</mi>
<mo fence="false" stretchy="false">}</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle i\in \{1,\dotsc ,m\}}</annotation>
</semantics>
</math></span><img src="./6d7a25137e9baaf70273ac4d1c5fa1a23b13b4f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.349ex; height:2.843ex;" alt="{\displaystyle i\in \{1,\dotsc ,m\}}" loading="lazy"></span>, let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i}\colon \Omega \to \mathbb {R} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>:<!-- : --></mo>
<mi mathvariant="normal">Ω<!-- Ω --></mi>
<mo stretchy="false">→<!-- → --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">R</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle a_{i}\colon \Omega \to \mathbb {R} }</annotation>
</semantics>
</math></span><img src="./f55b89469f76288c1148a6c8fd3ce9839c552e8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.034ex; height:2.509ex;" alt="{\displaystyle a_{i}\colon \Omega \to \mathbb {R} }" loading="lazy"></span> be additive set functions. Then <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(S)=\max _{i}a_{i}(S)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>f</mi>
<mo stretchy="false">(</mo>
<mi>S</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<munder>
<mo movablelimits="true" form="prefix">max</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</munder>
<msub>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<mi>S</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f(S)=\max _{i}a_{i}(S)}</annotation>
</semantics>
</math></span><img src="./5e301ed89f32065c47f9a88835dadb9cd9e4df5a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:17.737ex; height:4.009ex;" alt="{\displaystyle f(S)=\max _{i}a_{i}(S)}" loading="lazy"></span> is a subadditive set function.
</p><p>Fractionally subadditive set functions are a generalization of submodular functions and a special case of subadditive functions. A subadditive function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>f</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f}</annotation>
</semantics>
</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> is furthermore fractionally subadditive if it satisfies the following definition.<sup id="cite_ref-UF_1-1" class="reference"><a href="#cite_note-UF-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> For every <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\subseteq \Omega }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>S</mi>
<mo>⊆<!-- ⊆ --></mo>
<mi mathvariant="normal">Ω<!-- Ω --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle S\subseteq \Omega }</annotation>
</semantics>
</math></span><img src="./926e3bc2815ca680f0a752381de3770f44d16b5e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.276ex; height:2.343ex;" alt="{\displaystyle S\subseteq \Omega }" loading="lazy"></span>, every <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{1},\dotsc ,X_{n}\subseteq \Omega }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>X</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<msub>
<mi>X</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo>⊆<!-- ⊆ --></mo>
<mi mathvariant="normal">Ω<!-- Ω --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle X_{1},\dotsc ,X_{n}\subseteq \Omega }</annotation>
</semantics>
</math></span><img src="./8ae999a83682115afe9300bd4b6e83e4ed0db8d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.076ex; height:2.509ex;" alt="{\displaystyle X_{1},\dotsc ,X_{n}\subseteq \Omega }" loading="lazy"></span>, and every <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{1},\dotsc ,\alpha _{n}\in [0,1]}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>α<!-- α --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<msub>
<mi>α<!-- α --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo>∈<!-- ∈ --></mo>
<mo stretchy="false">[</mo>
<mn>0</mn>
<mo>,</mo>
<mn>1</mn>
<mo stretchy="false">]</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \alpha _{1},\dotsc ,\alpha _{n}\in [0,1]}</annotation>
</semantics>
</math></span><img src="./4ddda7fd8c4713484b7a68c3b58f3dbf6e8eb045.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.919ex; height:2.843ex;" alt="{\displaystyle \alpha _{1},\dotsc ,\alpha _{n}\in [0,1]}" loading="lazy"></span>, if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1_{S}\leq \sum _{i=1}^{n}\alpha _{i}1_{X_{i}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mn>1</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>S</mi>
</mrow>
</msub>
<mo>≤<!-- ≤ --></mo>
<munderover>
<mo>∑<!-- ∑ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</munderover>
<msub>
<mi>α<!-- α --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<msub>
<mn>1</mn>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>X</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 1_{S}\leq \sum _{i=1}^{n}\alpha _{i}1_{X_{i}}}</annotation>
</semantics>
</math></span><img src="./4d85217146656d64edc9f3ac543181728410010a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:14.963ex; height:6.843ex;" alt="{\displaystyle 1_{S}\leq \sum _{i=1}^{n}\alpha _{i}1_{X_{i}}}" loading="lazy"></span>, then <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(S)\leq \sum _{i=1}^{n}\alpha _{i}f(X_{i})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>f</mi>
<mo stretchy="false">(</mo>
<mi>S</mi>
<mo stretchy="false">)</mo>
<mo>≤<!-- ≤ --></mo>
<munderover>
<mo>∑<!-- ∑ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</munderover>
<msub>
<mi>α<!-- α --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mi>f</mi>
<mo stretchy="false">(</mo>
<msub>
<mi>X</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f(S)\leq \sum _{i=1}^{n}\alpha _{i}f(X_{i})}</annotation>
</semantics>
</math></span><img src="./9fa01b23dd323d6ac517dd92866d2ef72ef7b351.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:19.527ex; height:6.843ex;" alt="{\displaystyle f(S)\leq \sum _{i=1}^{n}\alpha _{i}f(X_{i})}" loading="lazy"></span>. The set of fractionally subadditive functions equals the set of functions that can be expressed as the maximum of additive functions, as in the example in the previous paragraph.<sup id="cite_ref-UF_1-2" class="reference"><a href="#cite_note-UF-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>
</p>
<div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2></div>
<ul><li><a href="Submodular_set_function" title="Submodular set function">Submodular set function</a></li>
<li><a href="Utility_functions_on_indivisible_goods" title="Utility functions on indivisible goods">Utility functions on indivisible goods</a></li></ul>
<div class="mw-heading mw-heading2"><h2 id="Citations">Citations</h2></div>
<style data-mw-deduplicate="TemplateStyles:r1239543626">
/* start https://en.wikipedia.org/ */
.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}
/* end https://en.wikipedia.org/ */
</style><div class="reflist">
<div class="mw-references-wrap"><ol class="references">
<li id="cite_note-UF-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-UF_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-UF_1-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-UF_1-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">
/* start https://en.wikipedia.org/ */
.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}
/* end https://en.wikipedia.org/ */
</style><cite id="CITEREFFeige2009" class="citation journal cs1"><a href="Uriel_Feige" title="Uriel Feige">Feige, Uriel</a> (2009). "On Maximizing Welfare when Utility Functions are Subadditive". <i>SIAM Journal on Computing</i>. <b>39</b> (1): <span class="nowrap">122–</span>142. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F070680977">10.1137/070680977</a>.</cite></span>
</li>
<li id="cite_note-DNS-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-DNS_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFDobzinskiNisanSchapira2010" class="citation journal cs1">Dobzinski, Shahar; <a href="Noam_Nisan" title="Noam Nisan">Nisan, Noam</a>; Schapira, Michael (2010). "Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders". <i><a href="Mathematics_of_Operations_Research" title="Mathematics of Operations Research">Mathematics of Operations Research</a></i>. <b>35</b> (1): <span class="nowrap">1–</span>13. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.79.6803">10.1.1.79.6803</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1060590.1060681">10.1145/1060590.1060681</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2685385">2685385</a>.</cite></span>
</li>
</ol></div></div></div><!--htdig_noindex--><div><div class="zim-footer">
This article is issued from <a class="external text" title="Last edited on 2025-02-19" href="https://en.wikipedia.org/wiki/?title=Subadditive_set_function&oldid=1276599942">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
</body></html>